package 数组;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/zero-matrix-lcci/
 */
public class _01_08_零矩阵 {
    /**
     * 利用两个标记数，记录首行和首列是否存在 0
     * 然后通过遍历判断各个行列是否存在 0， 然后再首行和首列加上标记0，可得当前行和当前列需要置为0
     * 最后遍历得0即可
     * @param matrix 目标矩阵
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol = false, flagRow = false;
        // 遍历查询矩阵中的第一列是否存在0，如果存在 则标记
        for (int[] ints : matrix) {
            if (ints[0] == 0) {
                flagCol = true;
                break;
            }
        }
        // 遍历查询矩阵中的第一行是否存在0，如果存在 则标记
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                flagRow = true;
                break;
            }
        }
        // 遍历查询中间是否存在为0的数  如果存在 则将目标值的第一行和第一列设置为0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 将存在0的行和列进行置空操作
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flagCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    }

    /**
     * 设置两个boolean的数组进行存储
     * @param matrix 目标矩阵
     */
    public void setZeroes2(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        // 定义两个存储是否含有0的数组
        boolean[] rowFlag = new boolean[n];
        boolean[] colFlag = new boolean[m];
        // 遍历判断是否存在0  如果存在 则存入对应的boolean数组中的下标
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (matrix[i][j] == 0) {
                    rowFlag[i] = colFlag[j] = true;
                }
            }
        }
        // 遍历查看 boolean 数组 如果存在0 则将该值为 0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rowFlag[i] || colFlag[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 利用一个标记数，记录首行和首列是否存在 0
     * 在第一个方法中进行优化  可以将row的判断符去掉
     * @param matrix 目标矩阵
     */
    public void setZeroes3(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol = false;
        // 遍历记录首列是否存在0  且 记录每个元素是否为0 如果为0  则将当前元素的首行 首列 设置为0
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                flagCol = true;
            }
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 遍历赋值 行和列为0  行需要从最后一行开始，然后向上遍历  否则会将矩阵所有元素置为0
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol) {
                matrix[i][0] = 0;
            }
        }
    }
}
